In typical processor installations wherein information is transmitted through a router, it is necessary, when multiple packets of information are destined for the same location, that each packet be transmitted in the order received. When there is but a single processing element at the router, this presents no problem. That is, if two packets P1 and P2 with the same destination address arrive at the same port at the router, with P1 arriving prior to P2, and if both of them are to be forwarded via the same port, then P1 should be transmitted prior to P2 on the destination port. That is, the router should not transmit P2 prior to transmitting P1. The departure order should be same as the arrival order. This is important because the final destination host, when it receives an out-of-order packet, implicitly assumes that the not-yet arrived prior packets are lost packets and proceeds with the assumption that network congestion is causing the packet loss and reduces its TCP (Transmission Control Protocol) window. This minimizes the effective communication bandwidth between the end points involved in the communication.
If there is only one processor element handling all the packets, then it processes the packets sequentially and, consequently, there is no problem in maintaining sequence. However, modern networking devices have multiple processing elements forwarding packets simultaneously to enable increased throughput.
As an example, consider the following situation:
Packet 1 and Packet 2 each have the same destination address and arrive in that same order at the same port. Packet 1 is assigned to PE 1 for processing and packet 2 is assigned to PE 2 for processing, the processing being necessary before the packets of data are forwarded. In general, it is possible for PE 2 to finish processing packet 2 sooner than PE 1 finishes processing its packet. If appropriate steps are not taken, PE 2 will transmit P2 out of the system before PE 1 is able to transmit P1. Such a scenario results in out-of-order delivery. This problem can be easily solved if there is but one processing element at the router, by completely processing the packets as they are received.
In IBM's PowerNP architecture wherein there are multiple processing elements, the problem of out-of-order delivery is solved by using completion unit labels. When a packet enters the system, before it is passed to one of the PEs, it is classified into a communication flow and assigned a “completion unit label”. Packets belonging to the same communication flow will receive the same completion unit label.
In the above example, P1 and P2 will receive the same completion unit label, and a linked list of PEs will be attached to this label. When P1 is assigned to PE T1, T1 will be in the head of the linked list. Later, when P2 is assigned to PE T2, T2 will be appended to the linked list in the end. When a PE finishes the processing of the packet, it will make an attempt to transmit the frame by invoking the command “enqueue with label”. This means that the completion unit will transmit the frame out of the port if, and only if, the PE that is making the “enqueue with label” attempt is at the head of the PE queue for the corresponding label. After transmitting the frame, the PE will be removed from the head of the PE queue. This is illustrated in FIG. 1.
As shown in FIG. 1, packets 1 and 2 belong to the same flow. Packet 1 arrives first and then packet 2 arrives. Packets 3 and 4 belong to the same flow. Packet 3 arrives first and then packet 4. Packet 1 gets assigned to the PE 1. The system assigns the label L1 to packets 1 and 2, since they belong to the same but different communication flow. Similarly, Label L2 is assigned to packets 3 and 4. (Typically, L1 will not be equal to L2.) PE 1 is at the head of the linked list for Label L1 since it was assigned the packet that came before. For the same reasons, PE 3 is at the head of the list for Label L2. When PEs finish processing, they are permitted to transmit the packets assigned to them if, and only if, they are at the head of the list. This prevents out-of-order transmission of packets.
However, this does not address the problem of packet fragmentation. That is, a PE is fragmenting the packet it is processing into multiple fragments, and the PE has to perform multiple “enqueue” operations to transmit all the fragments generated by it. That is, P1 and P2 arrive in order and are assigned to PEs PE1 and PE2. Now, PE1 decides to fragment P1 into P1-1, P1-2 . . . P1-m and, similarly, PE2 decides to fragment P2 into P2-1, P2-2 . . . P2n, respectively. The question arises how to maintain in sequence delivery without enforcing artificial sequencing. For example, transmitting all fragments of P1 prior to transmitting any of the fragments of P2 is quite restrictive. It is indeed required that P1-1 through P1-m be transmitted in the same order.